package com.worldcup.utils;

/**
 * @author duwan.zq
 * @date 2018/05/24
 */
public class StringUtils {

    /**
     * LevenshteinDistance算法实现，计算字符串相似度
     *
     * 参考https://en.wikipedia.org/wiki/Levenshtein_distance
     * @param s1
     * @param s2
     */
    public static double getLevenshteinDistance(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        int[][] dif = new int[len1 + 1][len2 + 2];
        for (int i = 0; i <= len1; i++) {
            dif[i][0] = i;
        }
        for (int i = 0; i <= len2; i++) {
            dif[0][i] = i;
        }
        //计算两个字符是否一样，计算左上的值
        int cost;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                cost = (s1.charAt(i - 1) == s2.charAt(j - 1) ? 0 : 1);
                //取三个值中最小的
                dif[i][j] =  Math.min(Math.min(dif[i-1][j] + 1, dif[i][j-1] + 1), dif[i-1][j-1] + cost);
            }
        }
        return 1 - (double)dif[len1][len2]/Math.max(len1, len2);
    }
}
